package com.note.feng.dataStructureAlgorithm.queue;

/**
 * 循环队列：
 *  循环队列的底层依然是数组，不过增加了指向头和尾的指针。
 *  front == tail 时队列为空
 *  (tail + 1) % c == front 队列为满，此时capacity预留一个空间不能使用
 * @param <E>
 */
public class LoopQueue <E> implements Queue<E>{

    private E [] data;
    private int front;
    private int tail;
    private int size;

    public LoopQueue(int capacity){
        data = (E[]) new Object[capacity + 1];
        front = 0;
        tail = 0;
        size = 0;
    }
    public LoopQueue(){
        this(10);
    }

    public int getCapacity(){
        return data.length - 1;
    }

    @Override
    public int getSize() {
        return size;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void enqueue(E e) {
        //队列满了，进行扩容操作
        if((tail + 1) % data.length == front){
            resize(getCapacity() * 2);
        }
        data[tail] = e;
        size ++;
        tail = (tail + 1) % data.length;
    }

    private void resize(int capacity) {
        E [] newData = (E[]) new Object[capacity + 1];
        for(int i = 0; i < size; i++){
            newData[i] = data[(1 + front) % data.length];
        }
        data = newData;
        front = 0;
        tail = size;
    }

    @Override
    public E dequeue() {
        if(isEmpty()){
            throw new RuntimeException("queue is empty");
        }
        E e = data[front];
        data[front] = null;
        front = (front + 1) % data.length;
        size --;
        //缩容操作
        if(size == getCapacity() / 4 && getCapacity() / 2 != 0){
            resize(getCapacity() / 2);
        }
        return e;
    }

    @Override
    public E getFront() {
        if(isEmpty()){
            throw new RuntimeException("queue is empty");
        }
        return data[front];
    }


}
